package com.dong.ch06_tree_bst;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
@Slf4j
public class BST<E extends Comparable<E>> {
    public class Node<E> {
        E e;
        Node<E> left;
        Node<E> right;

        public Node(E e) {
            this.e = e;
        }
    }
    private Node<E> root =null;
    private int size;

    public BST() {
        root=null;
        size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty() {
        return size==0;
    }
    public void add(E e) {
        if(root==null) {
            root=new Node<>(e);
            size++;
            return;
        }else {
            add(e,root);
        }
    }
    private void add(E e, Node<E> node) {
        int compareResult = e.compareTo(node.e);
        if(compareResult<0) {
            if(node.left==null) {
                node.left=new Node<>(e);
                size++;
            }else {
                add(e,node.left);
            }
        }else if(compareResult>0) {
            if(node.right==null) {
                node.right=new Node<>(e);
                size++;
            }else {
                add(e,node.right);
            }
        }else {
            System.out.println(e+"---> already exist!");
        }
    }
    public void add2(E e) {
        add2(e,root);
    }
    private Node<E> add2(E e, Node<E> node) {
        if(node==null) {
            size++;
            return new Node<>(e);
        }
        int compareResult = e.compareTo(node.e);
        if(compareResult<0) {
            node.left = add2(e,node.left);
        }else if(compareResult>0) {
            node.right=add2(e,node.right);
        }
        return node;
    }

    public void addNoneRecursive(E e) {
        if(root==null) {
            root=new Node<>(e);
            return;
        }
        Node<E> node = root;
        while(node!=null&&!node.e.equals(e)) {
            int compareResult = e.compareTo(node.e);
            if(compareResult<0) {
                if(node.left!=null) {
                    node=node.left;
                }else {
                    node.left=new Node<>(e);
                    size++;
                    break;
                }
            }else if(compareResult>0) {
                if(node.right!=null) {
                    node=node.right;
                }else {
                    node.right= new Node<>(e);
                    size++;
                    break;
                }
            }
        }
    }
    public boolean contains(E e) {
        return contains(e, root);
    }
    public boolean contains(E e ,Node<E> node) {
        if(node==null) {
            return false;
        }
        int compareResult = e.compareTo(node.e);
        if(compareResult==0) {
            return true;
        }else if(compareResult<0) {
            return contains(e,node.left);
        }else {
            return contains(e,node.right);
        }

    }

    /**
     * 遍历
     */
    public void preOrder() {
        preOrder(root);
    }
    public void preOrder(Node<E> node) {
        if(node==null) {
            return ;
        }else {
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    public void midOrder() {
        midOrder(root);
    }
    public void midOrder(Node<E> node) {
        if(node==null) {
            return ;
        }else {
            midOrder(node.left);
            System.out.println(node.e);
            midOrder(node.right);
        }
    }

    public static void main(String[] args) {

    }
    public static void testPrint() {
        BST<Integer> tree = new BST<>();
        int[] nums = {5,3,6,8,4,2};
        for (int num : nums) {
            tree.add(num);
        }
        tree.preOrder();
        System.out.println("*************");
        tree.traversePreNoneRecursive();
        System.out.println("*************");
        System.out.println(tree);
    }
    @Test
    public void testREmoveMin() {
        int nums = 1000;
        BST<Integer> bst = new BST<>();
        Random random = new Random();
        for (int i = 0; i < nums; i++) {
            bst.add(random.nextInt(nums*2));
        }
    //    System.out.println(bst);
        System.out.println("***************************************");
        while(!bst.isEmpty()) {
            System.out.println(bst.getMin().e);
            bst.deleteMin();
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return "BST{ size:+"+size+", node: \n "+sb.toString()+"}";
    }
    void generateBSTString(Node<E> node, int level , StringBuilder sb) {
        if(node==null) {
            sb.append(genPreStr(level)).append("null").append("\n");
            return;
        }
        sb.append(genPreStr(level)).append(node.e).append("\n");
        generateBSTString(node.left,level+1,sb);
        generateBSTString(node.right,level+1,sb);
    }
    String genPreStr(int level) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < level; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
    public void traversePreNoneRecursive() {
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node<E> node = stack.pop();
            System.out.println(node.e);
            if(node.right!=null) {
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
    }
    public void levelTraverse() {
        Queue<Node<E>> queue  = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.e);
            if(node.left!=null) {
                queue.add(node.left);
            }
            if(node.right!=null)  {
                queue.add(node.right);
            }
        }
    }
/*    public void deleteMin() {
        Node<E> current = root;
        while(current!=null&&current.left!=null) {
            if(current.left!=null) {
                if(current.left.left!=null) {
                    current =current.left;
                }else {
                    current.left=current.left.right;
                }
            }
        }
    }*/
    public void deleteMin() {
        root = deleteMin(root);
    }
    public Node<E> deleteMin(Node<E> node) {
        if(node.left==null) {
            Node<E> rightNode = node.right;
            node.right=null;
            size--;
            return rightNode;
        }else {
            node.left=deleteMin(node.left);
            return node;
        }
    }
    public void deleteMax() {
      root=  deleteMax(root);

    }
    public Node<E> deleteMax(Node<E> node) {
        if(node.right==null) {
            Node<E> leftNode= node.left;
            node.left=null;
            size--;
            return leftNode;
        }else {
            node.right=   deleteMax(node.right);
            return node;
        }
    }
    public Node<E> getMax(Node<E> node) {
        Node<E> current = node;
        Node lastNode = null;
        while(node!=null) {
            lastNode=node;
            node=node.right;
        }
        return lastNode;
    }
    public Node<E> getMin() {
        return getMin(root);
    }
    public Node<E> getMin(Node<E> node) {
        if(node==null) {
            return null;
        }
        Node<E> current = node;
        Node<E> lastNode=null;
        while(node!=null) {
            lastNode=node;
            node=node.left;
        }
        return lastNode;
    }
    public void deleteAny(E e) {
        Node<E> node = root;
        while(node!=null) {
            int compareResult = node.e.compareTo(e);
            if(compareResult<0) {
                node=node.left;
            }else if(compareResult>0) {
                node=node.right;
            }else {
                if(node.right!=null) {
                    Node<E> max = getMax(node.right);
                    node.e=max.e;
                    deleteMin(node.right);
                }else if(node.left!=null) {
                    Node<E> min = getMin(node.left);
                    node.e = min.e;
                    deleteMax(node.left);
                }else {
                    node=null;
                }
            }
        }
    }
    public String toPrettyString() {
        return "";
    }
    private int getMaxDeepLevel() {
        return -1;
    }

    /**
     * 寻找小于指定元素的最大值
     * @param e
     * @return
     */
    public E floor(E e) {
        Node<E> floor = null;
        Node<E> current = root;
        if(root==null) {
            return null;
        }
        floor=current;
        while(current!=null) {
            int compareResult = e.compareTo(current.e);
            if(compareResult<=0) {
                floor=current.left;
                current =current.left;
            }else {
                current = current.right;
            }
        }
        return null;
    }

    /**
     * 寻找大于指定元素的最小值
     * @param e
     * @return
     */
    public E ceil(E e) {
        Node<E> node = root;

        while(node!=null) {
            int compareResult = e.compareTo(node.e);
            if(compareResult==0) {
                return getMin(node.right).e;
            }else if(compareResult<0) {
                node=node.right;
            }else {  //>0
                node=node.left;
            }
        }
        return null;
    }


    /**
     * 排名
     * @param e
     * @return
     */
    public int rank(E e) {
        return -1;
    }

    /**
     * 寻找排名第n个
     * @param rank
     * @return
     */
    public E select(int rank) {
        return null;
    }
    //维护深度值
    //记录重复值个数 count

}
